遞迴的第一個題目是費氏數列!
這題也是在以前數學課的時候一定遇過的問題><
前面先來介紹一下什麼是費氏數列
再給大家看題目~

費氏數列

費波那契數列(Fibonacci Sequence)是一個著名的數學序列，以義大利數學家列昂納多·費波那契(Leonardo Fibonacci)的名字命名，這個數列在數學和計算機科學中有著廣泛的應用。
在《算術書》中，費波那契提出了一個關於兔子的繁殖問題來引入這個數列。問題的描述是：

"一對兔子被放在一個圓形的籠子裡，兔子每月都會生一對兔子。每對兔子從出生後的第二個月開始，每月也會生一對兔子。假設兔子永遠不會死亡，那麼第n個月的兔子數量是多少？"

透過這個問題，費波那契數列計算了兔子數量，隨著時間的變化，解決這個問題得到了數列 1,1,2,3,5,8,13,21,34,等等。

費氏數列的數學特性

1.黃金比例： 費波那契數列與黃金比例有關。當數列中的相鄰數字的比值趨近於黃金比例(約1.6180339887)時，這種關係在數學上稱為「黃金比例」

2.矩陣表示法：費波那契數列可以用矩陣表示法來描述，這種方法可以有效地計算數列中的第n項，並且在計算大數字時具有優勢

遞迴與動態規劃：除了基本的遞迴實現外，動態規劃也是計算費波那契數列的常見方法，它比簡單的遞迴方法更高效，因為它避免了重複的計算

費氏數列程式碼

函式的名字就取叫費波那契Fibonacci
基本情況是如果n=0，函式就return 0，這是第0個費波那契數
以及如果n=1，函式就return 1，這是第1個費波那契數
遞迴情況是除了0和1之外的其他n值，函式計算fibonacci(n-1)+fibonacci(n-2)的值，也就是n的前兩個費波那契數之和

接下來說明一下計算過程!
我用前三行輸出來做舉例

print(fibonacci(1)):函式被呼叫時n=1，基本情況n==1條件符合，所以回傳1

print(fibonacci(2)):函式被呼叫時n=2，這不是基本情況，所以函式計算fibonacci(1)+fibonacci(0)，fibonacci(1)回傳1，fibonacci(0)回傳0
所以fibonacci(2)回傳1+0=1。

print(fibonacci(3)):函式被呼叫時n=3，函式計算fibonacci(2)+fibonacci(1)
fibonacci(2)回傳1，fibonacci(1)回傳1
所以fibonacci(3)回傳1+1=2。

以此類推!

其實費波那契數列不只在數學中有重要的應用，也在自然界中有許多應用。像是植物的葉序、花瓣數量、果實排列等都可以用費波那契數列來描述
費波那契數列也在計算機科學、藝術、音樂等領域中具有應用價值喔!><